package likou;

import java.util.HashMap;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/4/21  9:22
 */
public class _1248 {
    public static int numberOfSubarrays2(int[] nums, int k) {
        if (nums.length == 0) {
            return 0;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        //统计奇数个数，相当于我们的 presum
        int oddnum = 0;
        int count = 0;
        map.put(0,1);
        for (int x : nums) {
            // 统计奇数个数
            oddnum += x & 1;
            // 发现存在，则 count增加
            if (map.containsKey(oddnum - k)) {
                count += map.get(oddnum - k);
            }
            //存入
            map.put(oddnum,map.getOrDefault(oddnum,0)+1);
        }
        return count;
    }

    public static int numberOfSubarrays(int[] nums, int k) {
        if (nums.length <= 0) {
            return 0;
        }
        int num = 0;//返回的答案
        int fontIndex;//最小子数组的前下标
        int lastIndex;//最小子数组的后下标
        int fontFIndex;//最小子数组前下标的前面第一个奇数的下标
        int lastLIndex;//最小子数组后下标的后面第一个奇数下标
        int jishuzu[] = new int[nums.length];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                jishuzu[j] = i;//记录下标
                j++;
            }
        }
        //开始计算
        //计算答案
        int qianShu = 0;
        int houShu = 0;
        for (int i = 0; i < j; i++) {
            //初始化数据
            lastIndex = jishuzu[i + k - 1];
            fontIndex = jishuzu[i];
            if (i == 0) {
                fontFIndex = 0;
                qianShu = fontIndex - fontFIndex;
            } else {
                fontFIndex = jishuzu[i - 1];
                qianShu = fontIndex - fontFIndex - 1;
            }
            if (i + k < jishuzu.length) {
                if (jishuzu[i + k] == 0) {
                    lastLIndex = jishuzu.length - 1;
                    houShu = lastLIndex - lastIndex;
                } else {
                    lastLIndex = jishuzu[i + k];
                    houShu = lastLIndex - lastIndex - 1;
                }
            } else {
                lastLIndex = jishuzu.length - 1;
                houShu = lastLIndex - lastIndex;
            }
            //结束标志
            if (lastIndex == 0 && i + k - 1 != 0) {//最小的子数组的后下标为0，自定义数组长度过长，不进行多余遍历
                break;
            }
            int zongShu = qianShu + houShu;
            if (qianShu == 0) {//如果前面没有数
                num += houShu + 1;
            } else {
                if (houShu == 0) {//如果后面没有数
                    num += qianShu + 1;
                } else {
                    num += zongShu + qianShu * houShu + 1;
                }
            }
        }
        return num;
    }

    public static void main(String[] args) {
//        int nums[] = {2, 2, 2, 1, 2, 2, 1, 2, 2, 2};
//        int k = 2;
//        int nums2[] = {2, 4, 6};
//        int k2 = 1;
//        int nums3[] = {1, 1, 2, 1, 1};
//        int k3 = 3;
//        System.out.println(numberOfSubarrays(nums, k));
//        System.out.println(numberOfSubarrays(nums2, k2));
//        System.out.println(numberOfSubarrays(nums3, k3));
        int nums4[] = {1, 0, 1,0,0, 1, 1};
        int k4 = 2;
        System.out.println(numberOfSubarrays2(nums4, k4));

    }
}
